package library;

public class mySort {
    //作用：对数组进行排序
    //描述：快速排序
    public static void quickSort(int[] arr, int l, int r) {
        if (l >= r) return;
        int pivot = arr[l], left = l, right = r;
        while (left < right) {
            while (left < right && arr[right] >= pivot) --right;
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) ++left;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        quickSort(arr, l, left - 1);
        quickSort(arr, left + 1, r);
    }

    public static void quickSort(long[] arr, int l, int r) {
        if (l >= r) return;
        long pivot = arr[l];
        int left = l, right = r;
        while (left < right) {
            while (left < right && arr[right] >= pivot) --right;
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) ++left;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        quickSort(arr, l, left - 1);
        quickSort(arr, left + 1, r);
    }

    public static void quickSort(char[] arr, int l, int r) {
        if (l >= r) return;
        char pivot = arr[l];
        int left = l, right = r;
        while (left < right) {
            while (left < right && arr[right] >= pivot) --right;
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) ++left;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        quickSort(arr, l, left - 1);
        quickSort(arr, left + 1, r);
    }


    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(long[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(char[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }


    //作用：堆数组进行排序
    //描述：堆排序
    //  对于以0编号为根节点的树
    //  parent(i) = (i-1)/2
    //  left(i) = 2*i+1
    //  right(i) = 2*i+2
    //向下调整start位置
    //offset偏移量，使得可以以任意节点作为起点
    public static void downAdjust(int[] arr, int start, final int end, final int offset) {
        int parentVal = arr[start + offset], child = start << 1 | 1;
        //将start向下查找插入位置，直到查到叶子节点或者已经是大根堆的小堆则停止
        while (child <= end) {
            //选择左右孩子中大的一个孩子
            if (child + offset < end && arr[child + offset] < arr[child + 1 + offset]) ++child;
            //如果父节点大于等于子节点中大的一个，说明调整完成
            if (parentVal >= arr[child + offset]) break;
            arr[start + offset] = arr[child + offset];
            start = child;
            child = start << 1 | 1;
        }
        arr[start + offset] = parentVal;
    }

    //建大根堆堆
    public static void makeHeap(int[] arr, final int start, final int end) {
        //从最后一个节点的父节点开始向下调整
        for (int i = (end - start - 1) >> 1; i >= 0; --i)
            downAdjust(arr, i, end, start);
    }

    public static void heapSort(int[] arr, final int start, int end) {
        makeHeap(arr, start, end);
        while (end > start) {
            Algorithm.swap(arr, start, end);
            downAdjust(arr, start, --end, start);
        }
    }
}